Scanners are devices that view an image and then represent it as if it were a number of adjacent lines of consecutive pixel positions along a line. The optical content at each pixel location is represented by a digital value (say, four or five bits), and the scanner""s output is often organized serially, as consecutive digital values delimited or grouped into collections representing the scanned lines. An important parameter in this process is the spatial density represented by consecutive digital values within a line, often expressed in dots per inch, or DPI. A similar parameter is the distance between adjacent lines, which may be termed lines per inch, or LPI. For most scanners the DPI and LPI are fixed during any given scanning operation; for certain scanners the LPI may vary in complicated ways if during scanning the LPI axis is allowed to depart from perpendicularity with the DPI axis. Sometimes firmware associated with preparing the gray scale data for use by another system re-formats the scanned results to appear as though they had been scanned at a lower resolution than actually performed by the hardware. In any event, the scanner system usually outputs pixel data that is expected to already conform, or that has been adjusted to conform, to a regular grid of pixel locations. For a variety of different light sensitive sensors, this scanning process is capable of very good performance under favorable conditions.
Leaving aside a host of performance affecting issues that stem from the nature of the light sensitive sensor, one very important issue attaches to the nature of the original image being scanned. As is well known, many images that begin as photographs are reproduced as half-tones. Under magnification the half-toning appears as a regularly spaced matrix of dots having different sizes. Upon such examination (say, with a magnifying glass) it is seen that dark dots are really no darker than light ones, but they are instead bigger. In fact, adjacent dark dots might be so large as to blend together, so that there is an absence of intervening white space. Really light dots are sufficiently small (to the point of absence, even) that they have lots of intervening white space.
Half-toning is often produced by the introduction of a screen in the optical path. The holes in the screen are apertures that produce the dots of varying size. The pitch of the screen (i.e., the number of holes per inch) determines (absent other enlargement or reduction) the spacing for the matrix of dots in the half-tone reproduction, which might be the printed image of a photograph in a newspaper or a magazine. The pitch of the screen is generally uniform in both directions. The screen used for newspaper photographs might be as coarse as eighty five lines per inch, or less, while that for an expensive magazine might be one hundred fifty lines per inch, or more.
Half-toning solves some otherwise very nasty problems in the reproduction of photographs, and is ubiquitous. Printers for a computer often imitate the half-tone process to increase the fidelity with which a regular office copier can reproduce the printer""s output of an image composed of elements besides the easy-to-copy solid lines or xe2x80x9ctypexe2x80x9d (e.g., the 100% solid go characters of a font).
Consider a laser printer. It might have an internal micro-dot resolution of 600 or 1200 DPI, which is used to create groups of larger dots of varying size. There are various known ways to take gray scale data for pixels at, say, one hundred dots per inch, and create from the micro-dots an image of larger variable size dots at, say, one hundred dots per inch. One of these process is known as xe2x80x9cordered ditheringxe2x80x9d, and uses the xe2x80x9cfine positionsxe2x80x9d (X and Y positions mod n) of an incoming pixel to address an n by n matrix of varying threshold values. If the gray scale value of the incoming pixel is at or above the threshold a corresponding cluster of micro-dots is produced. For fields of truly all white and truly solid black, this process produces true absence of micro-dots and solid micro-dots, respectively. For the levels of gray between those extremes there will be clusters of micro-dots of variable size. It is as if the printer had its own internal screen, although in most cases the screening agent is the software driver, and not the printer itself
Moire patterns are the familiar regular pattern of dark bands or spots distributed across an image containing two (or more) underlying quantization regimes, such as having been screened by two different screens of different pitch. The relative orientation of the two regimes (screens) has an influence on the shape of the Moire pattern produced. When an image is viewed through two misaligned or different screens the Moire pattern relies on a regular disturbance in image intensity to reveal itself. That is, if two cells of the screens are in good alignment the xe2x80x9clightxe2x80x9d for the corresponding subject matter xe2x80x9cgets through,xe2x80x9d, as if there were only one screen; any other alignment increasingly interferes with image fidelity during transmission of the image. Now, the case that will interest us the most concerns the viewing (say, by printing) of an original unscreened image through a second screen (in the printer) after it has already been half-toned with a first screen. We can dispense with the first screen if we take into account that what impinges on the second screen is a pattern of variable size dots, separated by, or on a field of, white space. As before, the dots in a region might be so large as to blot out the white space, or the dots might be so small that the region is entirely (or nearly) white space.
Thus, if the second screen aligns completely, or temporarily aligns well in a particular region, with the half-toned dots of the image, then within the region of good alignment there are no artifacts to disturb the transmission of the image; the dots of the image produce corresponding clusters of printed micro-dots. Now, suppose that the second screen is significantly or totally misaligned with the dots of the image. If the second screen is the same screen as the first, but simply translated out of maximum alignment (but not rotated), then the entire image would appear uniformly dim by an amount corresponding to the lack of alignment, as the apparent darkness or effective size of all the dots is uniformly reduced. If the second screen has a different pitch or is rotated, then there will be periodically occurring instances of good alignment interspersed with bad alignment. In regions of poor alignment the image either: (a) begins to wash out, as consecutive smallish dots fall in the spaces between consecutive apertures of the second screen (regularly fail to meet the threshold of the ordered dither); or (b) goes solid, as consecutive largish dots bridge across consecutive apertures of the second screen (regularly exceed the threshold of the ordered dither). In case (a) small dots are removed (and medium size dot made smaller), while in case (b) medium size dots are made into larger dots. These disturbances to dot size are the visible Moire pattern.
The scanning and subsequent printing of previously reproduced images is becoming more and more prevalent. Unfortunately, this can be accompanied by two undesirable outcomes.
Simply scanning a half-toned image can cause detectable Moire pattern artifacts in the data of the gray scale values for the scanned result. They emerge along the DPI direction at a first spatial frequency that is the difference between the half-toning screen""s effective pitch in that direction and the DPI of the scanner. They also emerge along the LPI direction at a second spatial frequency that is the difference between the half-toning screen""s effective pitch in that direction and the LPI of the scanner. In other words, the resolution of the scanner""s hardware acts as if it were a screen. Upon reflection it will be agreed it would be fair to call these xe2x80x9cscanner inducedxe2x80x9d Moire patterns.
More noticeable than xe2x80x9cscanner inducedxe2x80x9d Moire patterns is what happens when the scanned half-tone image is printed to a printer that handles gray scale data by creating its own half-tone presentation, as described above. The result is exactly like viewing the original (e.g., an unscreened photograph) through two different arbitrarily positioned screens. One of these screens was that used for the half-toning of the image on the document that was scanned. The other is the screening process used by the printer. Left untreated these Moire pattern artifacts are sometimes very pronounced, often to the point where the result is considered altogether unusable. It will be noted that this problem, which we may term a xe2x80x9cprinter inducedxe2x80x9d Moire pattern, is not the fault of the scanner. The scanner is more in the position of the messenger who gets the blame for bad news. After all, the location of one xe2x80x9cscreenxe2x80x9d is in the data that was scanned, the other xe2x80x9cscreenxe2x80x9d is in the printer, and the scanner is simply between the two.
The conventional cure for Moire artifacts is post-processing of the scanned data. This is computationally intensive, and adds considerably to the complexity of either the scanner or the environment expecting to use the data produced by the scanner. It can also reduce image resolution as a price paid for smoothing out the Moire patterns.
Consider a hand held scanning mechanism, such as the one described in the ""813 patent incorporated herein above. By way of example, suitable hand held scanning mechanisms include, but are not limited to, a CapShare 910 or CapShare 920 from Hewlett-Packard Co., which includes both an HP C6300A that is the actual scanner and some software to run on a PC.) That scanner uses a small (compared to the document) window (behind which is an array of optical sensors) in contact with the document and is moved by xe2x80x9cswipingxe2x80x9d in any at least slightly overlapping pattern until the whole document (or the portion of interest) has been covered. The scanner has an on-board navigation mechanism to track the swiping motion, a fair amount of memory and an impressive amount of processing power. It reconstructs, through processes called rectification (to keep the DPI and LPI axes perpendicular) and stitching (to assemble adjacent swipes into lines of correctly ordered pixels), the original image(s) that were swiped and outputs the reconstruction as if the data had been scanned by, say, a flatbed scanner. The actual scanning is 300 DPI along a line by a nominal 200 LPI, which is then rectified and stitched to be 300 DPI by 300 LPI. That result is then down-sampled to produce 150 DPI by 150 LPI of gray scale data. Since the swipes can be arbitrary in shape (simply squiggly, zig-zag or even U-shaped), one end of the line of sample pixels is often moving faster than the other, and an initial or internal 200 LPI criterion for sampling is driven by the end that is moving fastest. The handhold scanner is often used on material that contains halftone images. Regardless of its motion over the document (whether mostly straight or very squiggly) minor scanner-induced Moire artifacts will often emerge from scanning half-toned material, even after it has been rectified and stitched back together. We do not say that the scanning motion has no effect on scanner-induced and printer-induced Moire patterns; it certainly can have an effect by altering the apparent relative positions of the xe2x80x9cscreensxe2x80x9d. But the scanning motion is not the root cause of Moire patterns. Flatbed scanners also have the same difficulties.
It would be desirable if there were an effective and economical way of mitigating the effects of Moire patterns in the scanning and printing of half-toned images. That is, a way of mitigating the effects of scanner-induced Moire patterns in the data from the scanner, and printer-induced Moire patterns in the printed image. It would be particularly desirable if one relatively simple technique would mitigate both effects.
Both scanner-induced and printer-induced Moire patterns are significantly suppressed in a scanner that continuously varies its LPI. DPI in the direction different from the relative motion between the scanner and the document is generally a fixed property of the optical sensor, but in the LPI direction the distance between consecutive lines can be made to randomly vary between a maximum distance and a minimum distance. This spatially distributes the Moire effect, and prevents its concentrated accumulation into the usual recognizable two dimensional pattern.